package sort;


public class MergeSort {
    public static void main(String[] args) {
        int[] array = new int[]{5, 7, 4, 1, 2, 5, 15, 4, 8, 5, 6, 2, 5, 1, 4, 8, 2, 1, 4, 5, 2, 0, 45, 2};
        mergeSort(array);
        for (int i : array) {
            System.out.print(i + ",");
        }
    }

    private static void mergeSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        mergeSort(array, 0, array.length - 1);
    }

    private static void mergeSort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = (start + end) / 2;
        mergeSort(array, start, mid);
        mergeSort(array, mid + 1, end);
        //低位数组
        int low = start;
        //高位数组
        int high = mid + 1;
        int tempIndex = 0;
        int[] temp = new int[end - start + 1];
        while (low <= mid && high <= end) {
            if (array[low] < array[high]) {
                temp[tempIndex++] = array[low++];
            } else {
                temp[tempIndex++] = array[high++];
            }
        }
        //将剩余的数组搬到temp数组结尾
        while (low <= mid) {
            temp[tempIndex++] = array[low++];
        }
        while (high <= end) {
            temp[tempIndex++] = array[high++];
        }
        for (int i = 0; i < temp.length; i++) {
            array[i + start] = temp[i];
        }
    }
}
